package com.algorithm.arr;

/**
 * @Author: huangzhigao
 * @Date: 2021/3/1 22:57  给定一个数组，并给定其中的一个值，使小于等于该值的放左边，大于的放右边
 */
public class exchangeArrDemo {
    public static void sort(int arr[], int num) {
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < num) {
                //如果小于给定值，则将当前位置与index+1位置进行交换
                swap(i, index + 1, arr);
                index++;
            }
        }
    }


    /**
     * 荷兰国旗问题
     *
     * @param arr
     * @param num
     */
    public static void heLanFlag(int arr[], int num) {
        //与上述类似，定义两个指针
        int less = -1;
        int more = arr.length;
        int index = 0;
        //如果当前指定与右边大于的指针
        while (index < more) {
            if (arr[index] < num) {
                swap(index++, ++less, arr);
            } else if (arr[index] > num) {
                swap(--more, index, arr);
            } else {
                index++;
            }
        }

    }


    /**
     * 交换两数位置
     *
     * @param i
     * @param j
     * @param arr
     */
    public static void swap(int i, int j, int[] arr) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 2, 4};
        sort(arr, 5);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
